#include <iostream>
#include <stdlib.h>
#include "DynamicArray.h"

DynamicArray::DynamicArray(void (*ClearPtr)(ElementType))
{
    std::cout<<"调用构造函数"<<std::endl;
    size = 10;
    len = 0;
    dp = new ElementType[size];
    this->ClearPtr = ClearPtr;
}

DynamicArray::DynamicArray(const DynamicArray &array)
{
    std::cout<<"调用深拷贝函数"<<std::endl;
    len = array.len;
    size = array.size;
    dp = new ElementType[size];
    for(int i = 0; i < len ;i++)
    {
        dp[i] = array.dp[i];
    }
}

DynamicArray::~DynamicArray()
{
    std::cout<<"调用析构函数"<<std::endl;
    if(ClearPtr != NULL)
    {
        for(int i = 0; i < len; i++)
            ClearPtr(dp[i]);
    }
    delete []dp;
    size = 0;
    len = 0;
}

void DynamicArray::InsertTail(ElementType element)
{
    if(len == size)
    {
        size *= 2;
        ElementType *newPtr = new ElementType((void*)size);
        for(int i = 0; i < len; i++)
            newPtr[i] = dp[i];
        delete []dp;
        dp = newPtr;
    } 
    dp[len++] = element;
}

bool DynamicArray::RemoveByIndex(int index)
{
    if(index < 0 || index >= len)
    {
        std::cout<<"删除非法位置!"<<std::endl;
        return false;
    }
    if(this->ClearPtr != NULL)
    {
        this->ClearPtr(dp[index]);
    }
    for(int i = index; i < len; i++)
    {   
        dp[i] = dp[i+1];
    }
    len--;
    return true;
}

bool DynamicArray::RemoveByElement(ElementType element, bool (*funcPtr)(ElementType, ElementType), void (*ClearPtr)(ElementType))
{
    for(int i = 0; i < len; i++)
    {
        if(funcPtr(element,dp[i]) == true)
        {
            if(RemoveByIndex(i) == false)
            {
                return false;
            }
            i--;
        }
    }
    return true;
}

bool DynamicArray::RemoveFirstElement(ElementType element, bool (*funcPtr)(ElementType, ElementType), void (*ClearPtr)(ElementType))
{
    for(int i = 0; i < len; i++)
    {
        if(funcPtr(element,dp[i]) == true)
        {
            if(RemoveByIndex(i) == false)
            {
                return false;
            }
            return true;
        }
    }
    return false;
}

DynamicArray DynamicArray::FindElement(ElementType element, bool (*funcPtr)(ElementType, ElementType))
{
    DynamicArray ret = DynamicArray(this->ClearPtr);
    for(int i = 0; i < len; i++)
    {
        if(funcPtr(element,dp[i]) == true)
        {
            ret.InsertTail(dp[i]);
        }
    }
    return ret;
}

void FastSort(ElementType* s,int start, int end, bool (*funcptr)(ElementType, ElementType))
{
if(start >= end)
return;
ElementType temp = s[start];
int left = start;
int right = end;

while(left < right)
{
    while(left < right && funcptr(s[right],temp) == true)
    {
        right--;
    }
    if(left < right)
    {
        s[left] = s[right];
        left++;
    }
    while(left < right && funcptr(s[left],temp) == false)
    {
        left++;
    }
    if(left < right)
    {
        s[right] = s[left];
        right--;
    }
        s[left] = temp;
    }
    FastSort(s,start,left - 1,funcptr);
    FastSort(s,right + 1,end,funcptr);
}

void DynamicArray::Sort(bool (*funcPtr)(ElementType, ElementType))
{
    FastSort(dp,0,len - 1,funcPtr);
}

void DynamicArray::show(void (*printPtr)(ElementType))
{
    std::cout<<"size : "<<size<<" len : "<<len<<std::endl;
    for(int i = 0; i < len; i++)
    {
        // std::cout<<dp[i]<<" ";
        printPtr(dp[i]);
    }
    std::cout<<std::endl;
}